#include "common.h"
namespace common {
int partition(std::vector<int> &a, int begin, int end) {
    int index = rand() % (end - begin + 1) + begin; //[begin,end]
    int small = begin - 1;
    std::swap(a[index], a[end]);
    for (int index = begin; index < end; index++) {
        if (a[index] < a[end]) {
            small++;
            if (small != index)
                std::swap(a[index], a[small]);
        }
    }
    small++;
    std::swap(a[small], a[end]);
    return small;
}

int quickSelect(std::vector<int> &a, int left, int right, int index) {
    int idx = partition(a, left, right);
    if (idx == index) {
        return a[idx];
    } else {
        return idx < index ? quickSelect(a, idx + 1, right, index)
                           : quickSelect(a, left, idx - 1, index);
    }
}

int findKthLargest(std::vector<int> &nums, int k) {
    int left = 0;
    const int n = nums.size();
    int right = nums.size() - 1;
    return quickSelect(nums, left, right, n - k);
}
} // namespace common
